/*
题目: 替换后的最长重复字符
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

https://leetcode.cn/problems/longest-repeating-character-replacement/
 */
public class CharacterReplacement {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26]; // 窗口内记录每个字母的次数
        int maxn = 0; // 记录窗口内 某个字母 最大出现次数
        int left = 0;
        int n = s.length();

        for (int i = 0; i < n; i ++) {
            char ch = s.charAt(i);
            int pos = ch - 'A';

            freq[pos] ++;
            //这样做的意义：我们求的是最长，如果找不到更长的维持长度不变返回结果不受影响, 维持滑动窗口的不减性
            // 区分 AABB maxn = 2   和  ABCA , 后者 left ++ 后, maxn 受影响, 但是这样的滑动窗口会减少, 这种情况我们不关心
            maxn = Math.max(maxn, freq[pos]);

            // 窗口长度 - 窗口内最高频字母 = k 个 "万能钥匙"
            if (i - left + 1 - maxn > k) {
                freq[s.charAt(left) - 'A'] --;
                left ++;
            }
        }

        return n - left;
    }
}
